/*
题目: 和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
https://leetcode.cn/problems/subarray-sum-equals-k/
 */
public class SubarraySum {
    public int subarraySum(int[] nums, int k) {
        //前缀和 + 哈希
        Map<Integer, Integer> prefix = new HashMap<> (); //Key: 前缀和, Value: 路径个数
        prefix.put(0, 1); //提供前缀和为 0 的路径
        int curSum = 0;

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            res += prefix.getOrDefault(curSum - k, 0);

            prefix.put(curSum, prefix.getOrDefault(curSum, 0) + 1);
        }
        return res;
    }
}
